#include<iostream>

class Sort
{
public:
    Sort(int r[] , int n);  // 待排序的序列
    ~Sort();
    void InsertSort();  // 插入排序
    void ShellSort();   // 希尔排序
    void BubbleSort();  // 冒泡排序
    void QuickSort();   // 快速排序
    void SelectSort();  // 简单选择排序
    void HeapSort();    // 堆排序
    void MergeSort1(int first, int last);  // 二路归并（递归排序）
    void MergeSort2();  // 二路归并（非递归排序）
    void Print();       // 输出序列
private:
    int Partition(int first , int last);    // 快速排序，一次划分
    void Sift(int k , int last);            // 堆排序，堆调整
    void Merge(int first, int last1, int last2);    // 归并排序，一趟归并
    void MergePass(int h);  // 归并排序，一趟排序
    int * data;             // 待排序序列
    int length;             // 序列长度
};

Sort::Sort(int r[] , int n)
{
    data = new int (n);     // 申请n块整型动态内存
    for(int i = 0; i< n; i++)
        data[i] = r[i];
    length = n;
}

Sort::~Sort()
{
    delete[] data;
}

void Sort::Print()
{
    for(int i = 0; i < length; i++)
        std::cout << data[i] << "\t";
    std::cout << std::endl;
}

// 直接插入排序
void Sort::InsertSort()
{
    int i, j , temp;
    for(i = 1; i<length; i++)
    {
        temp = data[i];     // 暂存待插入记录
        for(j = i-1; j>=0 && temp<data[j]; j--) // 寻找插入位置
            data[j+1] = data[j];
        data[j+1] = temp;
    }
}

// 希尔排序
void Sort::ShellSort()
{
    int d,i,j,temp;
    for(d = length/2; d>=1; d = d/2)  // 增量为d，对整体直接插入排序
    {
        for(i = d; i<length; i++)   // 进行一趟希尔排序
        {
            temp = data[i];     // 暂存插入记录
            for(j = i-d; j>=0 && temp<data[j]; j=j-d)
                data[j+d] = data[j];    // 记录后移d个位置
            data[j+d] = temp;
        }
    }
}